/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 周斌
 * Date: 2024-07-16
 * Time: 20:43
 */
public class Test {
    //1.BM6判断链表中是否有环，利用快慢指针
    public boolean hasCycle(ListNode head) {
        if(head == null) {
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        //判断跳出循环的条件很重要，由于fast一次走两步
        //所以只需要考虑fast是否越界，fast不越界的话，那么slow更不会越界
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) {
                return true;
            }
        }
        return false;
    }
    //2.BM7链表中环的入口(让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针
    //都是每次均走一步，最终肯定会在入口点的位置相遇)
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null) {
            return null;
        }
        ListNode fast = pHead;
        ListNode slow = pHead;
        //判断跳出循环的条件很重要，由于fast一次走两步
        //所以只需要考虑fast是否越界，fast不越界的话，那么slow更不会越界
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                break;
            }
        }
        //判断跳出循环，说明没有环返回null，此处判断是因为上述有环的直接break了
        //所以需要再一次判断开区分是有环跳出循环的，还是无环跳出循环的。
        if(fast == null || fast.next == null) {
            return null;
        }
        //将slow这个指针重新放回head节点
        slow = pHead;
        while(fast != slow) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
    //3.BM8链表中倒数最后k个节点
    public ListNode FindKthToTail (ListNode pHead, int k) {
        if(pHead == null) {
            return null;
        }
        if(k-1 <= 0) {
            return null;
        }
        ListNode fast = pHead;
        ListNode slow = pHead;
        int count = 0;
        while(count != k - 1) {
            if(fast.next != null) {
                fast = fast.next;
                count++;
            } else {
                return null;
            }
        }
        //说明fast.next！= null，并且fast以及走了k-1步
        while(fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
    
}
